//二叉树的四种遍历

// #include "BiTNode.h"  在下面那个链队头文件中已经导入了，为防止重复导入，这里就注释掉了
#include "LinkQueue.h"
#include <iostream>

using namespace std;

void PreOrder(BiTree T) //先序遍历(根左右)
{
    if (T != nullptr)
    {
        cout << T->data;     //'根'：visit(T);(这里是输出该结点的数据域)
        PreOrder(T->lchild); //'左'：递归当前结点的左孩子
        PreOrder(T->rchild); //'右'：递归当前结点的右孩子
    }
    return;
}

void InOrder(BiTree T) //中序遍历(左根右)
{
    if (T != nullptr)
    {
        InOrder(T->lchild); //'左'：递归当前结点的左孩子
        cout << T->data;    //'根'：visit(T);(这里是输出该结点的数据域)
        InOrder(T->rchild); //'右'：递归当前结点的右孩子
    }
    return;
}

void PostOrder(BiTree T) //后序遍历(左右根)
{
    if (T != nullptr)
    {
        PostOrder(T->lchild); //'左'：递归当前结点的左孩子
        PostOrder(T->rchild); //'右'：递归当前结点的右孩子
        cout << T->data;      //'根'：visit(T);(这里是输出该结点的数据域)
    }
    return;
}

void LevelOrder(BiTree T) //层序遍历【BFS】
{
    LinkQueue Q;          //辅助队列Q
    InitQueue(Q);         //初始化队列Q
    BiTNode *p = nullptr; //用于承接队列中的二叉树结点
    EnQueue(Q, T);        //把二叉树的根节点压入队列
    while (!IsEmpty(Q))   //队列不为空，就一直执行
    {
        DeQueue(Q, p);            //出队并赋值给p
        cout << p->data;          // visit(p);(这里是输出该结点的数据域)
        if (p->lchild != nullptr) //把当前结点的左孩子压入队列
            EnQueue(Q, p->lchild);
        if (p->rchild != nullptr) //把当前结点的右孩子压入队列
            EnQueue(Q, p->rchild);
    }
    return;
}

int main()
{
    //二叉树T的初始化
    BiTree T = (BiTNode *)malloc(sizeof(BiTNode));
    InitT1(T); //初始化为ExampleTree1;

    //测试代码
    // PreOrder(T);
    // InOrder(T);
    // PostOrder(T);
    LevelOrder(T);
    return 0;
}